home *** CD-ROM | disk | FTP | other *** search
/ ftp.cs.arizona.edu / ftp.cs.arizona.edu.tar / ftp.cs.arizona.edu / tsql / doc / tsql.mail / 000044_kline _Thu Mar 18 15:00:48 1993.msg < prev    next >
Internet Message Format  |  1996-01-31  |  9KB
  1. Received: from cheltenham.cs.arizona.edu by optima.cs.arizona.edu (5.65c/15) via SMTP
  2.     id AA29083; Thu, 18 Mar 1993 15:00:49 MST
  3. Date: Thu, 18 Mar 1993 15:00:48 MST
  4. From: "Nick Kline" <kline>
  5. Message-Id: <199303182200.AA10374@cheltenham.cs.arizona.edu>
  6. Received: by cheltenham.cs.arizona.edu; Thu, 18 Mar 1993 15:00:48 MST
  7. To: tsql
  8. Subject: More proposed definitions
  9.  
  10. Here are more proposed glossary entries.  These definitions primarily
  11. concern aggregates in temporal query languages.
  12.  
  13.  
  14. -Nick Kline
  15. kline@cs.arizona.edu
  16.  
  17. \subsection{Partitioning Attribute}
  18.  
  19. The {\em partitioning attribute} is the attribute used to partition a
  20. relation into sets and is used in aggregation.  All members of a set
  21. have the same value for the partitioning attribute.  The sets are
  22. distinguished by different partitioning attribute values.
  23.  
  24.  
  25. \entry{Alternative Names}
  26.  
  27. Grouping attribute.
  28.  
  29. \entry{Discussion}
  30.  
  31. Grouping is the accepted term, but does not denote that the
  32. subdivision is into disjoint sets, while partitioning does imply this
  33. (-E3, +E9). The partitioning attribute may be composed of several
  34. attributes, as well as a single attribute.  If this is the case, then
  35. partition the relation based on the combination of the attribute
  36. values, where each unique combination of attribute values
  37. distinguishes a set.
  38.  
  39. The partitioning attribute is used only in value partitioning.
  40.  
  41.  
  42.  
  43. \subsection{Value Partitioning}
  44.  
  45. {\em Value partitioning} is the partitioning of a relation based on
  46. the value of the partitioning attribute or attributes, and is used in
  47. aggregation. All tuples within a set have the same partitioning
  48. attribute value.  
  49.  
  50. \entry{Alternative Names}
  51.  
  52. Value grouping.
  53.  
  54. \entry{Discussion}
  55.  
  56. Value grouping is awkward and does not adequately denote that the
  57. subdivision of the relation is into subsets where no two sets
  58. contain a common element.
  59.  
  60.  
  61. \subsection{Valid-time Grouping}
  62.  
  63. {\em Valid-time grouping} is the grouping of the valid
  64. time-line into {\em valid-time elements}, on each of which a
  65. cumulative aggregate may then be applied.  The valid-time elements may
  66. overlap and do not necessarily cover the time-line.  To compute the
  67. aggregate, first determine the valid-time elements of the grouping,
  68. then assemble the tuples valid over each valid-time element into a set, and
  69. finally compute the aggregate over each of these sets.  
  70.  
  71.  
  72. \entry{Alternative Names}
  73.  
  74. Valid-time partitioning.
  75.  
  76. \entry{Discussion}
  77.  
  78. Grouping the time-line is a useful capability for aggregates in
  79. temporal databases (+R1,+R3).
  80.  
  81. Partitioning is inappropriate because the valid-time elements may
  82. overlap; they do not necessarily form a {\it partition} since they may
  83. not cover the time-line.  One example of valid-time grouping is to
  84. divide the time-line into years, based on the Gregorian calendar. Then
  85. for each year, compute the count of the tuples which overlap that
  86. year.
  87.  
  88. There is no existing term for this concept.  There is no grouping
  89. attribute in valid-time grouping, since the grouping does not
  90. depend on attribute values, but instead on valid times.
  91.  
  92. Valid-time grouping may occur before or after value partitioning.
  93.  
  94. \subsection{Dynamic Valid-time Grouping}
  95.  
  96. In {\em dynamic valid-time grouping} the valid-time elements used in
  97. the grouping are determined solely from the timestamps of the relation
  98. being grouped.
  99.  
  100. \entry{Alternative Names}
  101.  
  102. Moving window.
  103.  
  104. \entry{Discussion}
  105.  
  106. The term dynamic is appropriate (as opposed to static) because if 
  107. the information in the database changes, the grouping intervals
  108. may change.  The intervals are determined from intrinsic information.
  109.  
  110. One example of dynamic valid-time grouping would be to compute the
  111. average value of an attribute in the relation (say the salary), for
  112. the previous year before the stop-time of each tuple.  A technique
  113. which could be used to compute this query would be for each tuple,
  114. find all tuples valid in the previous year before the stop-time of the
  115. tuple in question, and combine these tuples into a set.  Finally,
  116. compute the average of the salary attribute values in each set.
  117.  
  118.  
  119. It may seem inappropriate to use valid-time elements instead of
  120. intervals, however there is no reason to exclude valid-time elements as
  121. the time-line grouping may overlap in either case.
  122.  
  123. The existing term for this concept  does not have an opposing term
  124. suitable to refer to dynamic valid-time grouping, and may not
  125. distinguish between the two types of valid-time grouping (-E3, +E9).
  126. Various temporal query languages have used both dynamic and static
  127. valid-time grouping, but have not always been clear about which
  128. type of grouping they support (+E1).  Utilization of these terms
  129. will remove this ambiguity from future discussions.
  130.  
  131.  
  132. \subsection{Static Valid-time Grouping}
  133.  
  134. \entry{Definition}
  135.  
  136. In {\em static valid-time grouping} the valid-time elements used are
  137. determined solely from fixed points on a calendar, such as the start
  138. of each year.  The valid-time elements cover the valid time-line.
  139.  
  140. \entry{Alternative Names}
  141.  
  142. Moving window.
  143.  
  144. \entry{Discussion}
  145.  
  146. This term further distinguishes existing terms (-E3, +E9).  It is an
  147. obvious parallel to dynamic valid-time grouping (+E1).  Static is
  148. an appropriate term because the grouping intervals are determined
  149. from extrinsic information.  The grouping intervals would not
  150. change if the information in the database changed.
  151.  
  152. Computing the maximum salary of employees during each month is an
  153. example which requires using static valid-time grouping.  To compute
  154. this information, first divide the time-line into valid-time elements
  155. where each element represents a separate month on, say, the Gregorian
  156. calendar.  Then, find the tuples valid over each valid-time element,
  157. and compute the maximum aggregate over the members of each set.
  158.  
  159.  
  160. \subsection{Valid-time Cumulative Aggregation}
  161.  
  162. \entry{Definition}
  163.  
  164. In {\em cumulative aggregation}, for each valid-time element of the
  165. valid-time grouping (produced by either dynamic or static valid-time
  166. grouping), the aggregate is applied to all tuples associated with that
  167. valid-time element.
  168.  
  169. The value of the aggregate at any event is the value computed over the
  170. grouping element that contains that event.
  171.  
  172. \entry{Alternative Names}
  173.  
  174. Moving window.
  175.  
  176. \entry{Discussion}
  177.  
  178. {\em Cumulative} is used because the interesting values are defined
  179. over a cumulative range of time (+E8).  This term is more precise than
  180. the existing term (-E3, +E9).  Cumulative aggregation may be further
  181. restricted by valid-time grouping (c.f. static and dynamic valid-time
  182. grouping).   Instantaneous aggregation may be considered to be a
  183. degenerate case of cumulative aggregation.
  184.  
  185. One example of cumulative aggregation would be find the total number
  186. of employees who had worked at some point for a company.  To compute
  187. this value at the end of each calendar year, then, for each year,
  188. define a valid-time element which is valid from the beginning of time
  189. up to the end of that year.  For each valid-time element, find all
  190. tuples which overlap that element, and finally, count the number of
  191. tuples in each set.
  192.  
  193.  
  194. \subsection{Instantaneous Aggregation}
  195.  
  196. \entry{Definition}
  197.  
  198. In {\em instantaneous aggregation}, for each event on the valid
  199. time-line, the aggregate is applied to all tuples valid at that event.
  200.  
  201.  
  202.  
  203.  
  204. \entry{Alternative Names}
  205.  
  206. None.
  207.  
  208. \entry{Discussion}
  209.  
  210. The term {\em instantaneous} is appropriate because the aggregate is
  211. applied over an event.  It suggests an interest in the aggregate value
  212. over a very small time interval, an instant, much as acceleration is
  213. defined in physics over an infinitesimally small time (+R3).
  214.  
  215. Many temporal query languages perform instantaneous aggregation, others
  216. use cumulative aggregation, while still others use a combination of the two.
  217. This term will be useful to distinguish between the various alternatives,
  218. and is already used by some researchers (+R4,+E3).
  219.  
  220. \subsection{Gregorian Calendar}
  221.  
  222. \entry{Definition}
  223.  
  224. The {\em Gregorian calendar} is composed of 12 months, named in order,
  225. January, February, March, April, May, June, July, August, September,
  226. October, November, and December.  The 12 months form a year.  A year
  227. is either 365 or 366 days in length, where the extra day is used on
  228. ``leap years'', defined as years evenly divisible by 4, except for
  229. centesimal years divisible by 400.  Each month has a fixed number of
  230. days, except for February, the length of which varies by a day
  231. depending on whether or not the particular year is a leap year.
  232.  
  233.  
  234. \entry{Alternative Names}
  235.  
  236. None.
  237.  
  238. \entry{Discussion}
  239.  
  240. The Gregorian calendar is widely used and accepted (+E3,+E7).  This term is 
  241. defined and used elsewhere (-R1), but is in such common use in
  242. temporal databases that it should be defined.
  243.